package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Q1672 {

    /**
     * @param cards: 
     * @return: the minimal times to discard all cards
     */
	int min = 0;
    public int getAns(int[] cards) {
        // Write your code here
    	if(cards == null) {
    		return 0;
    	}
    	Set<Integer> set = new HashSet<>();
    	int [] nums = new int[10];
    	for(int i : cards) {
    		set.add(i);
    		nums[i] ++;
    	}
    	min = set.size();
    	search(nums, 0);
    	return min;
    }
    
    private void search(int[] nums, int sum) {

	    boolean flag = nums[4] == 0;
		int index1 = 0, index2 = 8;
		for (int i = 3; i >= 0; i--) 
			if (nums[i] == 0) {
				index1 = i;
				break;
			}
		for (int i = 5; i < 9; i++) 
			if (nums[i] == 0) {
				index2 = i;
				break;
			}
		if (flag || !flag && (index2 - index1) <= 5) {
			int res = 0;
			for (int i = 0; i < nums.length; i++)
				if (nums[i] != 0)
					res++;
			min = Math.min(min, res + sum);
			return;
		}
	    A:
	    for (int i = 0; i < 5; i++) {
	        int j = i, count = 0;
	        for (; j < nums.length; j++) {
	            if (nums[j] == 0 && j - i < 5)
	                continue A;
	            if (nums[j] == 0) {
	                count = j - i;
	            } else if (j == nums.length - 1)
	                count = j - i + 1;
	        }
	        while (count != 4) {
	            for (int k = i; k < i + count; k++)
	                nums[k]--;
	            search(nums, 1 + sum);
	            for (int k = i; k < i + count; k++)
	                nums[k]++;
	            count--;
	        }
	    }
	
    }

}
